sciencefandomcom_el-20200214-history
Αλγόριθμοι
Αλγόριθμοι Algorithms Ακολουθεί κατάλογος Αλγορίθμων κατά Επιστήμες. Combinatorial algorithms General combinatorial algorithms * Floyd's cycle-finding algorithm: finds cycles in iterations * (uniformly distributed) Pseudorandom number generators: ** Blum Blum Shub ** Mersenne twister ** Lagged Fibonacci generator ** Linear congruential generator * Robinson-Schensted algorithm: generates permutations from pairs of Young tableaux Graph algorithms * Αλγόριθμος Bellman-Ford : computes shortest paths in a weighted graph (where some of the edge weights may be negative) * Αλγόριθμος Dijkstra: computes shortest paths in a graph with non-negative edge weights * Perturbation methods: an algorithm that computes a locally shortest paths in a graph * Αλγόριθμος Floyd-Warshall: solves the all pairs shortest path problem in a weighted, directed graph * Αλγόριθμος Johnson : All pairs shortest path algorithm in sparse weighted directed graph * Αλγόριθμος Kruskal: finds a minimum spanning tree for a graph * Αλγόριθμος Prim: finds a minimum spanning tree for a graph * Αλγόριθμος Boruvka: finds a minimum spanning tree for a graph * Αλγόριθμος Ford-Fulkerson: computes the maximum flow in a graph * Αλγόριθμος Edmonds-Karp : implementation of Ford-Fulkerson * Nonblocking Minimal Spanning Switch say, for a telephone exchange * Αλγόριθμος Woodhouse-Sharp : finds a minimum spanning tree for a graph * Spring based algorithm: algorithm for graph drawing * Topological sort: finds linear order of nodes(e.g. jobs) based on their dependencies. * Hungarian algorithm: algorithm for finding a perfect matching * Coloring algorithm: Graph coloring algorithm. * Nearest neighbour algorithm * Αλγόριθμος Blur : Graphic Blur Algorithm. Ευριστικοί Αλγόριθμοι * Linear search: finds an item in an unsorted list * Selection algorithm: finds the k''th largest item in a list * Binary search algorithm: locates an item in a sorted list * Binary search tree: uses binary tree to maintain elements. * Breadth-first search: traverses a graph level by level * Depth-first search: traverses a graph branch by branch * Best-first search: traverses a graph in the order of likely importance using a priority queue * A* tree search: special case of best-first search that uses heuristics to improve speed * Uniform-cost search: a tree search that finds the lowest cost route where costs vary * Predictive search: binary like search which factors in magnitude of search term versus the high and low values in the search. Sometimes called dictionary search or interpolated search. * Hash table: finds an item in an unsorted collection in O(1) time. String algorithms Searching *Αλγόριθμος Aho-Corasick : trie based algorithm for finding all matches in dictionary. *Αλγόριθμος Bitap : fuzzy algorithm that determines strings are approximately equal. *Αλγόριθμος Boyer-Moore : amortised linear(sublinear in most times) algorithm *Αλγόριθμος Knuth-Morris-Pratt : bypasses reexamination of matched characters *Αλγόριθμος Rabin-Karp : searches multiple patterns efficiently *Longest common subsequence problem: Haskell's dynamic programming algorithm *Longest increasing subsequence problem *Shortest common supersequence problem *longest common substring problem *Αλγόριθμος Kadane: Finds Maximum Sub-Array of Any Size *Αλγόριθμος Horspool Approximate matching *Αλγόριθμος Hirschberg: space efficient algorithm for computing edit distance *Levenshtein edit distance *Metaphone: an algorithm for indexing words by their sound, when pronounced in English *Αλγόριθμος Needleman-Wunsch *NYSIIS: phonetic algorithm *Αλγόριθμος Smith-Waterman *Soundex Sorting algorithms * Binary tree sort * Bogosort * Bubble sort: for each pair of indices, swap the items if out of order * Bucket sort * Cocktail sort * Comb sort * Counting sort * Gnome sort * Heapsort: convert the list into a heap, keep removing the largest element from the heap and adding it to the end of the list * Insertion sort: determine where the current item belongs in the list of sorted ones, and insert it there * Merge sort: sort the first and second half of the list separately, then merge the sorted lists * Pancake sorting * Pigeonhole sort * Quicksort: divide list into two, with all items on the first list coming before all items on the second list.; then sort the two lists. Often the method of choice * Radix sort: sorts strings letter by letter * Selection sort: pick the smallest of the remaining elements, add it to the end of the sorted list * Shell sort: an attempt to improve insertion sort * Smoothsort * Topological sort Merge algorithms * Simple Merge algorithm * k-way Merge algorithm Compression algorithms Lossless compression algorithms * Burrows-Wheeler transform: preprocessing useful for improving lossless compression * DEFLATE: lossless data compression * Delta encoding: aid to compression of data in which sequential data occurs frequently * Dynamic Markov Compression: Compression using predictive arithmetic coding * Incremental encoding: delta encoding applied to sequences of strings * LZW: lossless data compression (Lempel-Ziv-Welch) * LZ77 (algorithm): LZ77 and LZ78 are the names for the two lossless data compression algorithms * LZMA: short for Lempel-Ziv-Markov chain-Algorithm * LZO: data compression algorithm that is focused on speed * PPM compression algorithm * Shannon-Fano coding * Truncated binary encoding * Run-length encoding: lossless data compression taking advantage of strings of repeated characters * SEQUITUR algorithm: lossless compression by incremental grammar inference on a string * EZW (Embedded Zerotree Wavelet) * Entropy encoding: coding scheme that assigns codes to symbols so as to match code lengths with the probabilities of the symbols ** Huffman coding: simple lossless compression taking advantage of relative character frequencies *** Adaptive Huffman coding: adaptive coding technique based on Huffman coding *** Package-Merge: Optimizes Huffman coding subject to a length restriction on code strings ** Arithmetic coding: advanced entropy coding *** Range encoding: same as arithmetic coding, but looked at in a slightly different way * Entropy coding with known entropy characteristics ** Unary coding: code that represents a number n with n ones followed by a zero ** Elias delta|gamma|omega coding: universal code encoding the positive integers ** Fibonacci coding: universal code which encodes positive integers into binary code words ** Golomb coding: form of entropy coding that is optimal for alphabets following geometric distributions ** Rice coding: form of entropy coding that is optimal for alphabets following geometric distributions Lossy compression algorithms * Linear predictive coding: lossy compression by representing the spectral envelope of a digital signal of speech in compressed form * Αλγόριθμος A-law : standard companding algorithm * Αλγόριθμος Mu-law : standard analog signal compression or companding algorithm * Fractal compression: method used to compress images using fractals * Transform coding: type of data compression for "natural" data like audio signals or photographic images * Vector quantization: technique often used in lossy data compression * Wavelet compression: form of data compression well suited for image compression (sometimes also video compression and audio compression) Computational geometry * Gift wrapping algorithm: determining the convex hull of a set of points * Αλγόριθμος Gilbert-Johnson-Keerthi : determining the smallest distance between two convex shapes. * Graham scan determining the convex hull of a set of points in the plane * Line segment intersection finding whether lines intersect with a sweep line algorithm. * Point in polygon: tests whether a given point lies within a given polygon * Αλγόριθμος Fortune: a well-known and simple-to-understand algorithm for computing Voronoi diagrams from a set of sites Computer graphics * Αλγόριθμος Bresenham: plots points of a 2-dimensional array to form a straight line between 2 specified points (uses decision variables) * Line drawing algorithm: graphical algorithm for approximating a line segment on discrete graphical media. * DDA line algorithm: plots points of a 2-dimensional array to form a straight line between 2 specified points (uses floating-point math) * Flood fill: fills a connected region of a multi-dimensional array with a specified symbol * Αλγόριθμος Xiaolin Wu: algorithm for line antialiasing. * Painter's algorithm: detects visible parts of a 3-dimensional scenery * Ray tracing: realistic image rendering * Phong shading: an illumination model and an interpolation method in 3D computer graphics * Gouraud shading: an algorithm to simulate the differing effects of light and colour across the surface of an object in 3D computer graphics * Scanline rendering: constructs an image by moving an imaginary line over the image * Global illumination algorithms: Considers direct illumination and reflection from other objects. * Interpolation: Constructing new data points such as in digital zoom. * Spline interpolation: Reduces error with Runge's phenomenon. * gatopeich's line algorithm: plots points of a 2-dimensional array to form a straight, symmetric line between 2 specified points (fast, simple, integer math). Computer vision * Epitome: represent an image or video by a smaller image or video. * Counting objects in an image: Counts the number of objects in a binary image. Uses the connected-component labeling algorithm to first label each object. Then returns the number of labeled objects. Cryptographic algorithms * Symmetric (secret key) encryption: ** Advanced Encryption Standard (AES), winner of NIST competition, also known as Rijndael ** Blowfish ** Data Encryption Standard (DES), sometimes DE Algorithm, winner of NBS selection competition, replaced by AES for most purposes ** IDEA ** RC4 (cipher) ** Tiny Encryption Algorithm * Asymmetric (public key) encryption: ** DSA ** ElGamal ** RSA ** Diffie-Hellman key exchange ** NTRUEncrypt * Cryptographic Message digest functions: ** MD5 – Note that there is now a method of generating collisions for MD5 ** RIPEMD-160 ** SHA-1 ** HMAC: keyed-hash message authentication ** Tiger (TTH), usually used in Tiger tree hashes * Cryptographically secure pseudo-random number generators ** Blum Blum Shub - based on the hardness of factorization ** Αλγόριθμος Yarrow ** Fortuna, allegedly an improvement on Yarrow algorithm ** Linear feedback shift register *Secret sharing, Secret Splitting, Key Splitting, M of N algorithms ** Shamir's Scheme ** Blakey's Scheme * ''Other ** Diffie-Hellman: key exchange Digital signal processing * CORDIC: Fast trigonometric function computation technique. * Rainflow-counting algorithm: Reduces a complex stress history to a count of elementary stress-reversals for use in fatigue analysis * Osem: algorithm for processing of medical images * Goertzel algorithm Can be used for DTMF digit decoding. * Discrete Fourier transform: determines the frequencies contained in a (segment of a) signal ** Fast Fourier transform ** Cooley-Tukey FFT algorithm ** Rader's FFT algorithm ** Bluestein's FFT algorithm ** Bruun's FFT algorithm ** Prime-factor FFT algorithm * Richardson-Lucy deconvolution: image de-blurring algorithm * Elser Difference-Map Algorithm: X-Ray diffraction microscopy Software engineering * Algorithms for Recovery and Isolation Exploiting Semantics: recovery * Unicode Collation Algorithm * CHS conversion: Converting between disk addressing systems * Cyclic redundancy check: calculation of a check word * Parity: Simple/fast error detection technique. Distributed systems algorithms * Lamport ordering: a partial ordering of events based on the happened-before relation * Snapshot algorithm: a snapshot is the process of recording the global state of a system * Vector clocks: a total ordering of events * Αλγόριθμος Marzullo: distributed clock synchronization * intersection algorithm: Another clock agreement algorithm. * Byzantine fault tolerance: Good fault tolerance. Memory Allocation and deallocation algorithms * Boehm garbage collector: Conservative garbage collector * Buddy memory allocation: Algorithm to allocate memory such that fragmentation is less. * Generational garbage collector: Fast garbage collectors that segregate memory by age * Mark and sweep * Reference counting Operating systems algorithms * Αλγόριθμος Banker: Algorithm used for deadlock avoidance. * Page replacement algorithms: Selecting the victim page under low memory conditions. * Αλγόριθμος Bully: Selecting new leader among many computers. 'Disk scheduling algorithms:' * Elevator algorithm: Disk scheduling algorithm that works like an elevator. * Shortest seek first: Disk scheduling algorithm to reduce seek time. 'Process synchronisation algorithms:' * Αλγόριθμος Peterson * Lamport's Bakery algorithm * Αλγόριθμος Dekker 'Scheduling algorithms' * Rate-monotonic scheduling * Earliest deadline first scheduling * Fair-share scheduling * Round-robin scheduling * Multi level feedback queue * shortest job next * shortest remaining time * Least slack time scheduling * List scheduling 'Electronics and hardware algorithms' * Αλγόριθμος Quine-McCluskey : Also called as Q-M algorithm, programmable method for simplyfying the boolean equations. * Petrick's method: Another algorithm for boolean simplification. * Espresso heuristic logic minimization: Fast algorithm for boolean function minimization. Medical algorithms * Ιατρικός Αλγόριθμος * Texas Medication Algorithm Project Neural networks * Hopfield net * Backpropagation * Self-organizing map Genetic Algorithms * Fitness proportionate selection - also known as roulette-wheel selection * Truncation selection * Tournament selection * Stochastic universal sampling Numerical algebra * Αλγόριθμος Buchberger: finds a Gröbner basis * Eigenvalue algorithm * Exponentiating by squaring: quickly computes powers of numbers and matrices * Gram-Schmidt process: orthogonalizes a set of vectors * Knuth-Bendix completion algorithm: for rewriting rule systems * Multivariate division algorithm: for polynomials in several indeterminates Number theoretic algorithms * Discrete logarithm: ** Baby-step giant-step ** Pollard's rho algorithm for logarithms ** Pohlig-Hellman algorithm ** Index calculus algorithm * Ευκλείδειος Αλγόριθμος : computes the greatest common divisor * Extended Euclidean algorithm: Also solves the equation ax+by = c. * Binary gcd algorithm: Efficient way of calculating gcd. * Integer factorization: breaking an integer into its prime factors ** prime factorization algorithm ** Fermat's factorization method ** Trial division ** Lenstra elliptic curve factorization ** Pollard's rho algorithm ** Pollard's p-1 algorithm ** Congruence of squares ** Quadratic sieve ** Αλγόριθμος Dixon ** Special number field sieve ** General number field sieve * Multiplication algorithms: fast multiplication of two numbers * Booth's multiplication algorithm * Primality tests: determining whether a given number is prime ** AKS primality test ** Miller-Rabin primality test ** Sieve of Eratosthenes ** Sieve of Atkin Numerical algorithms * Biconjugate gradient method: solves systems of linear equations * Dancing Links: finds all solutions to the exact cover problem * Αλγόριθμος De Boor : computes splines * Αλγόριθμος De Casteljau: computes Bézier curves * False position method: approximates roots of a function * Gauss-Jordan elimination: solves systems of linear equations * Αλγόριθμος Gauss-Legendre : computes the digits of pi * Kahan summation algorithm: a more accurate method of summing floating-point numbers * Levinson recursion: solves equation involving a Toeplitz matrix * MISER algorithm: Monte Carlo simulation, numerical integration * Newton's method: finds zeros of functions with calculus * Rounding functions: the classic ways to round numbers * Secant method: approximates roots of a function * Shifting nth-root algorithm: digit by digit root extraction * Square root: approximates the square root of a number * Strassen algorithm: faster matrix multiplication * Symbolic Cholesky decomposition: Efficient way of storing sparse matrix * Αλγόριθμος Risch : Translates indefinite integral to algebraic problem * Αλγόριθμος Borwein: an algorithm to calculate the value of 1/π * Αλγόριθμος Metropolis-Hastings : used to generate a sequence of samples from the probability distribution of one or more variables Optimization algorithms * Ant colony optimization * BFGS method: A nonlinear optimization algorithm * Branch and bound * Chain matrix multiplication * Conjugate gradient * Differential evolution * Evolution strategy * Αλγόριθμος Gauss-Newton : An algorithm for solving nonlinear least squares problems. * Genetic algorithms * Gradient descent * Interior point method * Αλγόριθμος Karmarkar: The first reasonably efficient algorithm that solves the linear programming problem in polynomial time. * Αλγόριθμος Levenberg-Marquardt: An algorithm for solving nonlinear least squares problems. * Line search * Local search * Nelder-Mead method (downhill simplex method): A nonlinear optimization algorithm. * Newton's method in optimization * Particle swarm * Random-restart hill climbing * Simplex algorithm: An algorithm for solving the linear programming problem * Simulated annealing * Stochastic tunneling * Subset sum algorithm * Tabu search Parsing * Recursive descent parser: A top-down parser suitable for LL(k'') grammars * LL parser: A relatively simple linear time parsing algorithm for a limited class of context-free grammars * LR parser: A more complex linear time parsing algorithm for a larger class of context-free grammars. Variants: ** Operator-precedence parser ** SLR (Simple LR) parser ** LALR (Look-ahead LR) parser ** Canonical LR parser * Packrat parser: A linear time parsing algorithm supporting some context-free grammars and parsing expression grammars * CYK algorithm: An O(n3) algorithm for parsing any context-free grammar * Earley parser: Another O(n3) algorithm for parsing any context-free grammar * GLR parser:An algorithm for parsing any context-free grammar by Masaru Tomita. It is tuned for deterministic grammars, on which it performs almost linear time and O(n3) in worst case. * Inside-outside algorithm: An O(n3) algorithm for re-estimating production probabilities in probabilistic context-free grammars Quantum algorithms ''Application of quantum computation to various categories of problems and algorithms * Αλγόριθμος Grover: provides quadratic speedup for many search problems * Αλγόριθμος Shor: provides exponential speedup for factorizing a number * Αλγόριθμος Deutsch-Jozsa: criterion of balance for Boolean function Theory of computation and automata * Powerset construction: Algorithm to convert nondeterministic automaton to deterministic automaton. * Αλγόριθμος Todd-Coxeter : Procedure for generating cosets. Other *Alpha max plus beta min algorithm: an approximation of the square-root of the sum of two squares. *Astronomical algorithms *Αλγόριθμος Baum-Welch : hidden markov models *Bit manipulation algorithms: Create bit mask algorithm *Doomsday algorithm: day of the week *Αλγόριθμος Schreier-Sims *Αλγόριθμος Viterbi : hidden markov models *Xor swap algorithm: swaps the values of two variables without using a buffer *Αλγόριθμος Luhn : a method of validating identification numbers *Αλγόριθμος Rutishauser *Αλγόριθμος Stemming: a method of reducing words to their stem, base, or root form *Hamming weight (population count): find the number of 1 bits in a binary word *Αλγόριθμος Gerchberg–Saxton : Phase retrieval algorithm for optical planes *Shunting yard algorithm: convert an infix-notation math expression to postfix Εσωτερική Αρθρογραφία * Αλγόριθμος * Βιβλιογραφία * * Ιστογραφία *Ομώνυμο άρθρο στην Βικιπαίδεια *Ομώνυμο άρθρο στην Livepedia *[ ] *[ ] *